#include <iostream>
#include <cstring>
using namespace std;
int pell(int n,int cache[]){
	if(n==1){
		return 1;
	}
	if(n==2){
		return 2;
	}
	if(cache[n]==-1){
		cache[n]=(2*pell(n-1,cache)+pell(n-2,cache))%32767;
	}
	return cache[n];
}

int main(){
	int n,s,max=-1;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
        if(a[i]>max){
			max=a[i];
		}
	}
	int cache[max+1];
	memset(cache,-1,sizeof(cache));
	for(int i=0;i<n;i++){
		s=pell(a[i],cache);
		cout<<s<<endl;
	}
	return 0;
}
